// #include<iostream>
// #include<vector>
// using namespace std;
// //递归写法
// int fib(int n)
// {
//     //边界条件
//     if(n == 0) return 0;
//     if(n == 1) return 1;
//     //非边界条件
//     return fib(n - 1) + fib(n - 2);
// }
// //这个程序的时间复杂度：满叉树的节点数 2^n - 1;
// //时间复杂度 2^n
// //时间复杂度：这么高的原因：有很多次重复计算
// //优化：搞一个存储表

// //从上到下
// //记忆化搜索
// int fib1(int n,vector<int>& dp)
// {
//     //将存储表中的值都初始化为 - 1
//     if(n == 0) return 0;
//     if(n == 1) return 1;
//     //查表
//     if(dp[n] !=  -1)
//     {
//         return dp[n];
//     }
//     int ans = fib1(n - 1,dp) + fib1(n - 2,dp);
//     //建表
//     dp[n] = ans; 
//     return ans;
// }
// //记忆化搜索的时间复杂度：O(n)


// int fib2(int n)
// {
//     vector<int> dp;
//     dp[0] = 0;
//     dp[1] = 1;
//     for(int i = 2;i <= n;i++)
//     {
//         dp[i] = dp[i - 1] + dp[i - 2];
//     }
//     return dp[n];
// }

// //没有必要使用两个数组，使用两个变量即可
// int fib3(int n)
// {
//     if(n == 0) return 0;
//     if(n == 1) return 1;
//     int LL = 0,l = 1;
//     for(int i = 2,cur; i <= n;i++)
//     {
//         cur = LL + l;
//         LL = l;
//         l = cur;
//     }
//     return l;
// }

// int main()
// {
//      return 0;
// }
